Besson T.,CNRS Orleans Fundamental Informatics Laboratory |
Durand-Lose J.,CNRS Orleans Fundamental Informatics Laboratory
Journal of Cellular Automata | Year: 2017
In the context of abstract geometrical computation, signal machines have been developed as a continuous counterpart of cellular automata capturing the notions of particles, signals and collisions. An important issue is the automatic generation of a CA mimicking the dynamics of a given signal machine. On the one hand, ad hoc/manual conversions exist. On the other hand, it is not always possible since some signal machines exhibit behaviors (like fractal constructions or relying on an unbounded density of information) that are just impossible with (discrete) cellular automata. This article provides a solution to automatically generate a cellular automata for a “maximal” class of signal machines that cannot exhibit such behaviors. This scheme encompasses the discretization of initial configuration so that the original continuous dynamics and the discrete one generated are identical up to a linear deformation. The considered signal machines are the ones that use only three speeds and allow only rational speeds and initial positions. Signals in these machines are always trapped inside a regular mesh. The construction relies on generating the corresponding discrete mesh. The soundness of the construction is proved and experimental results are provided. ©2017 Old City Publishing, Inc.
Lalande J.-F.,CNRS Orleans Fundamental Informatics Laboratory |
Wendzel S.,Fraunhofer Institute for Communication, Information Processing and Ergonomics
Proceedings - 2013 International Conference on Availability, Reliability and Security, ARES 2013 | Year: 2013
Covert channels enable a policy-breaking communication not foreseen by a system's design. Recently, covert channels in Android were presented and it was shown that these channels can be used by malware to leak confidential information (e.g., contacts) between applications and to the Internet. Performance aspects as well as means to counter these covert channels were evaluated. In this paper, we present novel covert channel techniques linked to a minimized footprint to achieve a high covertness. Therefore, we developed a malware that slowly leaks collected private information and sends it synchronously based on four covert channel techniques. We show that some of our covert channels do not require any extra permission and escape well know detection techniques like TaintDroid. Experimental results confirm that the obtained throughput is correlated to the user interaction and show that these new covert channels have a low energy consumption - both aspects contribute to the stealthiness of the channels. Finally, we discuss concepts for novel means capable to counter our covert channels and we also discuss the adaption of network covert channel features to Android-based covert channels. © 2013 IEEE.
Rouzaud-Cornabas J.,CNRS Orleans Fundamental Informatics Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011
With the number of services using virtualization and clouds growing faster and faster, it is common to mutualize thousands of virtual machines within one distributed system. Consequently, the virtualized services, softwares, hardwares and infrastructures share the same physical resources, thus the performance of one depends of the resources usage of others. We propose a solution for vm load balancing (and rebalancing) based on the observation of the resources quota and the dynamic usage that leads to better balancing of resources. As it is not possible to have a single scheduler for the whole cloud and to avoid a single point of failure, our scheduler uses distributed and collaborative scheduling agents. We present scenarios simulating various cloud resources and vm usage experimented on our testbed p2p architecture. © 2011 Springer-Verlag Berlin Heidelberg.
Petitjean S.,CNRS Orleans Fundamental Informatics Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2014
XMG (eXtensible MetaGrammar) is a metagrammar compiler which has already been used for the design of large scale Tree Adjoining Grammars and Interaction Grammars. Due to the heterogeneity in the field of grammar development (different grammar formalisms, different languages, etc), a particularly interesting aspect to explore is modularity. In this paper, we discuss the different spots where this modularity can be considered in a grammar development, and its integration to XMG. © 2014 Springer-Verlag Berlin Heidelberg.
Durand-Lose J.,CNRS Orleans Fundamental Informatics Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2013
Space-time diagrams of signal machines on finite configurations are composed of interconnected line segments in the Euclidean plane. As the system runs, a network emerges. If segments extend only in one or two directions, the dynamics is finite and simplistic. With four directions, it is known that fractal generation, accumulation and any Turing computation are possible. This communication deals with the three directions/speeds case. If there is no irrational ratio (between initial distances between signals or between speeds) then the network follows a mesh preventing accumulation and forcing a cyclic behavior. With an irrational ratio (here, the Golden ratio) between initial distances, it becomes possible to provoke an accumulation that generates infinitely many interacting signals in a bounded portion of the Euclidean plane. This behavior is then controlled and used in order to simulate a Turing machine and generate a 25-state 3-speed Turing-universal signal machine. © 2013 Springer-Verlag.
Robillard S.,CNRS Orleans Fundamental Informatics Laboratory
Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014 | Year: 2015
Catamorphisms are a class of higher-order functions that recursively traverse an inductive data structure to produce a value. An important result related to catamorphisms is the fusion theorem, which gives sufficient conditions to rewrite compositions of catamorphisms. We use the Coq proof assistant to automatically define a catamorphism and a fusion theorem according to an arbitrary inductive type definition. Catamorphisms are then used to define functional specifications and the fusion theorem is applied to derive efficient programs that match those specifications. © 2014 IEEE.
Le Gloannec B.,CNRS Orleans Fundamental Informatics Laboratory |
Ollinger N.,CNRS Orleans Fundamental Informatics Laboratory
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2012
Substitutions generate hierarchical colorings of the plane. Despite the non-locality of substitution rules, one can extend them by adding compatible local matching rules to obtain locally checkable colorings as the set of tilings of finite tileset. We show that for 2×2 substitutions the resulting tileset can furthermore be chosen strongly deterministic, a tile being uniquely determined by any two adjacent edges. A tiling by a strongly deterministic tileset can be locally reconstructed starting from any infinite path that cross every line and column of the tiling. © 2012 Springer-Verlag.
Gaspers S.,Vienna University of Technology |
Liedloff M.,CNRS Orleans Fundamental Informatics Laboratory
Discrete Mathematics and Theoretical Computer Science | Year: 2012
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V n D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1,4423 n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non-trivial algorithm computing a minimum independent dominating set of a graph in time O(1,3569 n). Furthermore, we give a lower bound of σ(1,3247 n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight. © 2012 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Montealegre P.,CNRS Orleans Fundamental Informatics Laboratory |
Todinca I.,CNRS Orleans Fundamental Informatics Laboratory
Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | Year: 2016
We present deterministic constant-round protocols for the graph connectivity problem in the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts a single sublinear size message to all other nodes. Communication rounds are synchronous. This model is sometimes called the broadcast congested clique. Specifi- cally, we exhibit a deterministic protocol that computes the connected components of the input graph in [1/ϵ] rounds, each player communicating O(nϵ · log n) bits per round, with 0 < ϵ ≤ 1. We also provide a deterministic one-round protocol for connectivity, in the model when each node receives as input the graph induced by the nodes at distance at most r > 0, and communicates O(n1/r · log n) bits. This result is based on a d-pruning protocol, which consists in successively removing nodes of degree at most d until obtaining a graph with minimum degree larger than d. Our technical novelty is the introduction of deterministic sparse linear sketches: a linear compression function that permits to recover sparse Boolean vectors deterministically. © 2016 ACM.
Goles E.,Adolfo Ibáñez University |
Montealegre P.,CNRS Orleans Fundamental Informatics Laboratory
Theoretical Computer Science | Year: 2014
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the And or the Or logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. © 2014 Elsevier B.V.