Laboratoire d'Informatique Fondamentale d'Orléans

International audience

We evaluated currents induced by expression of human homologs of Orai together with STIM1 in human embryonic kidney cells. When co-expressed with STIM1, Orai1 induced a large inwardly rectifying Ca(2+)-selective current with Ca(2+)-induced slow inactivation. A point mutation of Orai1 (E106D) altered the ion selectivity of the induced Ca(2+) release-activated Ca(2+) (CRAC)-like current while retaining an inwardly rectifying I-V characteristic. Expression of the C-terminal portion of STIM1 with Orai1 was sufficient to generate CRAC current without store depletion. 2-APB activated a large relatively nonselective current in STIM1 and Orai3 co-expressing cells. 2-APB also induced Ca(2+) influx in Orai3-expressing cells without store depletion or co-expression of STIM1. The Orai3 current induced by 2-APB exhibited outward rectification and an inward component representing a mixed calcium and monovalent current. A pore mutant of Orai3 inhibited store-operated Ca(2+) entry and did not carry significant current in response to either store depletion or addition of 2-APB. Analysis of a series of Orai1-3 chimeras revealed the structural determinant responsible for 2-APB-induced current within the sequence from the second to third transmembrane segment of Orai3. The Orai3 current induced by 2-APB may reflect a store-independent mode of CRAC channel activation that opens a relatively nonselective cation pore.

We use the notion of potential maximal clique to characterize the maximal cliques appearing in minimal triangulations of a graph. We show that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We prove that for all classes of graphs for which polynomial algorithms computing the treewidth and the minimum fill-in exist, we can list their potential maximal cliques in polynomial time. Our approach unifies these algorithms. Finally we show how to compute in polynomial time the potential maximal cliques of weakly triangulated graphs for which the treewidth and the minimum fill-in problems were open.

Modern malware uses advanced techniques to hide from static and dynamic analysis tools. To achieve stealthiness when attacking a mobile device, an effective approach is the use of a covert channel built by two colluding applications to exchange data locally. Since this process is tightly coupled with the used hiding method, its detection is a challenging task, also worsened by the very low transmission rates. As a consequence, it is important to investigate how to reveal the presence of malicious software using general indicators, such as the energy consumed by the device. In this perspective, this paper aims to spot malware covertly exchanging data using two detection methods based on artificial intelligence tools, such as neural networks and decision trees. To verify their effectiveness, seven covert channels have been implemented and tested over a measurement framework using Android devices. Experimental results show the feasibility and effectiveness of the proposed approach to detect the hidden data exchange between colluding applications.

We obtain an algorithmic metatheorem for the following optimization problem. Let $\varphi$ be a counting monadic second order logic (CMSO) formula and $t\geq 0$ be an integer. For a given graph $G=(V,E)$, the task is to maximize $|X|$ subject to the following: there is a set $ F\subseteq V$ such that $X\subseteq F $, the subgraph $G[F]$ induced by $F$ is of treewidth at most $t$, and the structure $(G[F],X)$ models $\varphi$, i.e., $(G[F],X)\models\varphi$. We give an algorithm solving this optimization problem on any $n$-vertex graph $G$ in time ${\cal O}(|\Pi_G| \cdot n^{t+4}\cdot f(t,\varphi))$, where $\Pi_G$ is the set of all potential maximal cliques in $G$ and $f$ is a function of $t$ and $\varphi$ only. Pipelined with the known bounds on the number of potential maximal cliques in different graph classes, there are a plethora of algorithmic consequences extending and subsuming many known results on polynomial-time algorithms for graph classes. We also show that all potential maximal cliques of $G$ can be enumerated in time ${\cal O}(1.7347^n)$. This implies the existence of an exact exponential algorithm of running time ${\cal O}(1.7347^n)$ for many NP-hard problems related to finding maximum induced subgraphs with different properties.

Please cite the following published version: https://doi.org/10.1016/j.physa.2022.127798 rather than this one

We study the P_4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4-domination in perfect graphs. This class strictly contains the P_4-extendible graphs and the P_4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4-tidy graphs and P_4-lite graphs are closely related. Note that the class of P_4-lite graphs is a class of brittle graphs strictly containing the P_4-sparse graphs defined by Hoang in [14]. McConnel & Spinrad [2] and independently Cournier & Habib [5] have shown that the modular decomposition tree of any graph is computable in linear time. For recognizing in linear time P_4-tidy graphs, we apply a method introduced by Giakoumakis in [9] and Giakoumakis & Fouquet in [6] using modular decomposition of graphs and we propose linear algorithms for optimization problems on such graphs, as clique number, stability number, chromatic number and scattering number. We show that the Hamiltonian Path Problem is linear for this class of graphs. Our study unifies and generalizes previous results of Jamison & Olariu ([18], [21], [22]), Hochstattler & Schindler[16], Jung [25] and Hochstattler & Tinhofer [15].

Ray casting on graphics processing units (GPUs) opens new possibilities for molecular visualization. We describe the implementation and calculation of diverse molecular representations such as licorice, ball-and-stick, space-filling van der Waals spheres, and approximated solvent-accessible surfaces using GPUs. We introduce HyperBalls, an improved ball-and-stick representation replacing tubes, linking the atom spheres by hyperboloids that can smoothly connect them. This type of depiction is particularly useful to represent dynamic phenomena, such as the evolution of noncovalent bonds. It is furthermore well suited to represent coarse-grained models and spring networks. All these representations can be defined by a single general algebraic equation that is adapted for the ray-casting technique and is well suited for execution on the GPU. Using GPU capabilities, this implementation can routinely, accurately, and interactively render molecules ranging from a few atoms up to huge macromolecular assemblies with more than 500,000 particles. In simple cases, based only on spheres, we have been able to display up to two million atoms smoothly.

Combining molecular dynamics simulations with user interaction would have various applications in both education and re- search. By enabling interactivity the scientist will be able to visualize the experiment in real time and drive the simulation to a desired state more easily. However, interacting with systems of interesting size requires significant computing resources due to the complexity of the simulation. In this paper, we propose an approach to combine a classical parallel molecular dynamics simulator, Gromacs, to a 3D virtual reality environment allowing to steer the simulation through external user forces applied with an haptic device to a selection of atoms. We specifically focused on minimizing the intrusion in the simulator code, on efficient parallel data extraction and filtering to transfer only the necessary data to the visualization environment, and on a controlled asynchronism between various components to improve interactivity. We managed to steer molecular systems of 1.7 M atoms at about 25 Hz using 384 CPU cores. This framework allowed us to study a concrete scientific problem by testing one hypothesis of the transport of an iron complex from the exterior of the bacteria to the periplasmic space through the FepA membrane protein.

Net Juggler is an open source library that turns a commodity component cluster running the VR Juggler platform on each node into a single VR Juggler image cluster. Application parallelization is transparent to the user and leads to high performance executions even with limited bandwidth networks.

Android malware authors use sophisticated techniques to hide the malicious intent of their applications. They use cryptography or obfuscation techniques to avoid detection during static analysis. They can also avoid detection during a dynamic analysis. Frequently, the malicious execution is postponed as long as the malware is not convinced that it is running in a real smartphone of a real user. However, we believe that dynamic analysis methods give good results when they really monitor the malware execution. In this article1, we propose a method to enhance the execution of the malicious code of unknown malware. We especially target malware that have triggering protections, for example branching conditions that wait for an event or expect a specific value for a variable before triggering malicious execution. In these cases, solely executing the malware is far from being sufficient. We propose to force the triggering of the malicious code by combining two contributions. First, we define an algorithm that automatically identifies potentially malicious code. Second, we propose an enhanced monkey called GroddDroid, that stimulates the GUI of an application and forces the execution of some branching conditions if needed. The forcing is used by GroddDroid to push the execution flow towards the previously identified malicious parts of the malware and execute it. The source code for our experiments with GroddDroid is released as free software2. We have verified on a malware dataset that we investigated manually that the malicious code is accurately executed by GroddDroid. Additionally, on a large dataset of 100 malware we precisely identify the nature of the suspicious code and we succeed to execute it at 28%.

The QCSP + language we introduce extends the framework of Quantified Constraint Satisfaction Problems (QCSPs) by enabling us to neatly express restricted quantifications via a chain of nested CSPs to be interpreted as alternately conjuncted and disjuncted. Restricted quantifiers turn out to be a convenient solution to the crippling modeling issues we encounter in QCSP and—surprisingly— they help to reuse propagation technology and to prune the search space. Our QCSP + solver—which also handles arithmetic and global constraints— exhibits state-of-the-art performances. 1

In this paper, we propose QUANTMINER, a mining quantitative association rules system. This system is based on a genetic algorithm that dynamically discovers “good ” intervals in association rules by optimizing both the support and the confidence. The experiments on real and artificial databases have shown the usefulness of QUANTMINER as an interactive, exploratory data mining tool.

Abstract. This paper presents the clustering algorithm PoBOC (Pole-Based Overlapping Clustering). It has two main characteristics: the number of final clusters is unknown a priori and PoBOC allows an object to belong to one or several clusters. Given a similarity matrix over a set of objects, PoBOC builds small and homogeneous sets of objects (the poles), and then it assigns the objects to the poles. The clustering method is evaluated on two different research areas. First, on the Rule-Based Learning (RBL) task: classification rules are generated by organizing the instances of a class so that each cluster is covered with a single rule; PoBOC is compared with different clustering methods and usual classifiers, on traditional datasets from the UCI repository. Otherwise, we observe the behaviour of PoBOC on the structuring of textual data in a semantic way. The efficiency of the proposed method on the two applications leads to conclude that PoBOC is also a general algorithm. 1

In imbalanced classification tasks, the training datasets may show class overlapping and classes of low density. In these scenarios, the predictions for the minority class are impaired. Although assessing the imbalance level of a training set is straightforward, it is hard to measure other aspects that may affect the predictive performance of classification algorithms in imbalanced tasks. This paper presents a set of measures designed to understand the difficulty of imbalanced classification tasks by regarding on each class individually. They are adapted from popular data complexity measures for classification problems, which are shown to perform poorly in imbalanced scenarios. Experiments on synthetic datasets with different levels of imbalance, class overlapping and density of the classes show that the proposed adaptations can better explain the difficulty of imbalanced classification tasks.

If $G$ is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings $M_1,...,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of them and Berge conjectured that its edge set can be covered by 5 perfect matchings. We define $τ(G)$ as the least number of perfect matchings allowing to cover the edge set of a bridgeless cubic graph and we study this parameter. The set of graphs with perfect matching index 4 seems interesting and we give some informations on this class.

International audience

Deep Learning (DL) techniques are now widespread and being integrated into many important systems. Their classification and recognition abilities ensure their relevance for multiple application domains far beyond pure signal processing. As a machine-learning technique that relies on training instead of explicit algorithm programming they offer a high degree of productivity. But recent research has shown that they can be vulnerable to attacks and the verification of their correctness is only just emerging as a scientific and engineering possibility. Moreover DL tools are not integrated into classical software engineering so software tools to specify, modify and verify them would make them even more mainstream as software-hardware systems. This paper surveys recent work and proposes research directions and methodologies for this purpose.

For over a decade, MapReduce has become a prominent programming model to handle vast amounts of raw data in large scale systems. This model ensures scalability, reliability and availability aspects with reasonable query processing time. However these large scale systems still face some challenges: data skew, task imbalance, high disk I/O and redistribution costs can have disastrous effects on performance. In this paper, we introduce MRFA-Join algorithm: a new frequency adaptive algorithm based on MapReduce programming model and a randomised key redistribution approach for join processing of large-scale datasets. A cost analysis of this algorithm shows that our approach is insensitive to data skew and ensures perfect balancing properties during all stages of join computation. These performances have been confirmed by a series of experimentations.

In this paper, we present a general scheme for incremental constraint retraction algorithms that encompasses all existing algorithms. Moreover, we introduce some necessary conditions to ensure the correctness of any new incremental constraint retraction algorithms. This rather theoretical work is based on the notion of explanation for constraint programming and is exemplified within the PALM system: a constraint solver allowing dynamic constraint retractions.