Search

Linked lists have always been an excellent teaching tool in programming.The question arises as to whether it is really worthwhile to use linked lists in the programs we run on a daily basis.It seems that in most cases array-based data structures are more advantageous, both in terms of memory space and, most importantly, in terms of execution speed.While it is easy to calculate the complexity of the operations, what about the actual execution efficiency?In this paper we try to answer this question by introducing a new benchmark.Our survey compares several linked-list implementations with some array-based implementations.We also propose a new array-based data structure that is well suited for list operations.; Les listes chaînées constituent depuis toujours un excellent exercice d'apprentissage de la programmation.En ce qui concerne l'utilisation des listes chaînées dans les programmes que nous utilisons au jour le jour, la question se pose de savoir s'il est vraiment rentable ou non d'utiliser des listes chaînées.Il semble que, dans la plupart des cas, les structures de données à base de tableaux sont plus avantageuses à la fois en terme de place mémoire, mais aussi et surtout en terme de vitesse d'exécution.Même s'il est facile de calculer la complexité des opérations, qu'en est-il vraiment de l'efficacité en cas d'exécution réelle?Ici, nous cherchons à répondre à cette question en introduisant un nouveau benchmark.Notre étude confronte différentes implantation de liste chaînée avec quelques implantations à base de tableaux.Nous proposons également une nouvelle structure d'implantation à base de tableaux bien adaptée aux opérations propres aux listes.

International audience; Modern verification projects continue to offer new challenges for formal verification. One of them is the linked list module of Contiki, a popular open-source operating system for the Internet of Things. It has a rich API and uses a particular list representation that make it different from the classical linked list implementations. Being widely used in the OS, the list module is critical for reliability and security. A recent work verified the list module using ghost arrays. This article reports on a new verification effort for this module. Realized in the Frama-C/Wp tool, the new approach relies on logic lists. A logic list provides a convenient high-level view of the linked list. The specifications of all functions are now proved faster and almost all automatically, only a small number of auxiliary lemmas and a couple of assertions being proved interactively in Coq. The proposed specifications are validated by proving a few client functions manipulating lists. During the verification, a more efficient implementation for one function was found and verified. We compare the new approach with the previous effort based on ghost arrays, and discuss the benefits and drawbacks of both techniques.

International audience; Internet of Things (IoT) applications are becoming increasingly critical and require formal verification. Our recent work presented formal verification of the linked list module of Contiki, an OS for IoT. It relies on a parallel view of a linked list via a companion ghost array and uses an inductive predicate to link both views. In this work, a few interactively proved lemmas allow for the automatic verification of the list functions specifications, expressed in the acsl specification language and proved with the Frama-C/Wp tool. In a broader verification context, especially as long as the whole system is not yet formally verified, it would be very useful to use runtime verification , in particular, to test client modules that use the list module. It is not possible with the current specifications, which include an inductive predicate and axiomatically defined functions. In this early-idea paper we show how to define a provably equivalent non-inductive predicate and a provably equivalent non-axiomatic function that belong to the executable subset e-acsl of acsl and can be transformed into executable C code. Finally, we propose an extension of Frama-C to handle both axiomatic specifications for deductive verification and executable specifications for runtime verification.

International audience; Internet of Things (IoT) applications are becoming increasingly critical and require rigorous formal verification. In this paper we target Contiki, a widely used open-source OS for IoT, and present a verification case study of one of its most critical modules: that of linked lists. Its API and list representation differ from the classical linked list implementations, and are particularly challenging for deductive verification. The proposed verification technique relies on a parallel view of a list through a companion ghost array. This approach makes it possible to perform most proofs automatically using the Frama-C/WP tool, only a small number of auxiliary lemmas being proved interactively in the Coq proof assistant. We present an elegant segment-based reasoning over the companion array developed for the proof. Finally, we validate the proposed specification by proving a few functions manipulating lists.

A multi-link system is defined as any finite number of rigid bodies interconnected by pairs with various constraints. Typical examples are the mechanisms in machines and limbs of humans. Recently, there is a need for parallel-mechanisms which have the advantages of maneuverability, lightness and stiffness. Many studies on them have been performed. Also, there are many studies on the motion control and motion analysis of living mechanisms. This paper describes an analytical approach to the kinematics and dynamics of a multi-link system using motor algebra. The redundant degrees of freedom arising from the analysis on the velocity motor, acceleration motor and force-moment motor are discussed. Throughout this paper, all the solutions of analysis are obtained by the linear calculation algorithms, such as QR decomposition, Gaussian elimination and backsubstitution. The data structure and the algorithms are based on linked lists.

© ACM, 2007. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in EMSOFT 2007.; International audience; The soundness of device drivers generally cannot be verified in isolation, but has to take into account the reactions of the hardware devices. In critical embedded systems, interfaces often were simple "volatile" variables, and the interface specification typically a list of bounds on these variables. Some newer systems use "intelligent" controllers that handle dynamic worklists in shared memory and perform direct memory accesses, all asynchronously from the main processor. Thus, it is impossible to truly verify the device driver without taking the intelligent device into account, because incorrect programming of the device can lead to dire consequences, such as memory zones being erased. We have successfully verified a device driver extracted from a critical industrial system, asynchronously combined with a model for a USB OHCI controller. This paper studies this case, as well as introduces a model and analysis techniques for this asynchronous composition.

International audience; We address the problem of verifying programs manipulating one-selector linked data structures. We propose and study in detail an application of counter automata as an accurate abstract model for this problem. We let control states of the counter automata correspond to abstract heap graphs where list segments without sharing are collapsed, and use counters to keep track of the number of elements in these segments. As a significant theoretical result, we show that the obtained counter automata are bisimilar to the original programs. Moreover, from a practical point of view, our translation allows one to apply efficient automatic analysis techniques and tools developed for counter automata (integer programs) in order to verify both safety as well as termination of list-manipulating programs. As another theoretical contribution, we prove that if the control of the generated counter automata does not contain nested loops (i.e., these automata are flat), both safety and termination are de-cidable for the original programs. Subsequently, we generalise our counter-automata-based model to keep track of ordering properties over lists storing ordered data. Finally, we show effectiveness of our approach by verifying automatically safety as well as termination of several sorting programs.

International audience; We address the problem of automatic verification of programs with dynamic data structures. We consider the case of sequential, non-recursive programs manipulating 1-selector-linked structures such as traditional linked lists (possibly sharing their tails) and circular lists. We propose an automata-based approach for a symbolic verification of such programs using the regular model checking framework. Given a program, the configurations of the memory are systematically encoded as words over a suitable finite alphabet, potentially infinite sets of configurations are represented by finite-state automata, and statements of the program are automatically translated into finite-state transducers defining regular relations between configurations. Then, abstract regular model checking techniques are applied in order to automatically check safety properties concerning the shape of the computed configurations or relating the input and output configurations. For that, we introduce new techniques for the computation of abstractions of the set of reachable configurations, and to refine these abstractions if spurious counterexamples are detected. Finally, we present experimental results showing the applicability of the approach and its efficiency.