Abstract We introduce a new abstract domain for analyzing memory block manipulations, focusing on programs with dynamically allocated arrays. This domain computes properties universally quantified over the value of the loop counters, both for assignments and tests. These properties consist of equalities and comparison predicates involving abstract expressions, represented as affine forms in the loop counters and symbolic dereferences. All these methods have been incorporated within the © static analyzer that checks for the absence of run-time errors in embedded critical software. We also give insights on how to implement this abstract domain within any other C static analyzer.

International audience

Hepatic stellate cells (HSC) are the source of extracellular matrix (ECM) whose overproduction leads to fibrosis, a condition that impairs liver functions in chronic liver diseases. Understanding the dynamics of HSCs will provide insights needed to develop new therapeutic approaches. Few models of hepatic fibrosis have been proposed, and none of them include the heterogeneity of HSC phenotypes recently highlighted by single-cell RNA sequencing analyses. Here, we developed rule-based models to study HSC dynamics during fibrosis progression and reversion. We used the Kappa graph rewriting language, for which we used tokens and counters to overcome temporal explosion. HSCs are modeled as agents that present seven physiological cellular states and that interact with (TGFβ1) molecules which regulate HSC activation and the secretion of type I collagen, the main component of the ECM. Simulation studies revealed the critical role of the HSC inactivation process during fibrosis progression and reversion. While inactivation allows elimination of activated HSCs during reversion steps, reactivation loops of inactivated HSCs (iHSCs) are required to sustain fibrosis. Furthermore, we demonstrated the model's sensitivity to (TGFβ1) parameters, suggesting its adaptability to a variety of pathophysiological conditions for which levels of (TGFβ1) production associated with the inflammatory response differ. Using new experimental data from a mouse model of CCl4-induced liver fibrosis, we validated the predicted ECM dynamics. Our model also predicts the accumulation of iHSCs during chronic liver disease. By analyzing RNA sequencing data from patients with non-alcoholic steatohepatitis (NASH) associated with liver fibrosis, we confirmed this accumulation, identifying iHSCs as novel markers of fibrosis progression. Overall, our study provides the first model of HSC dynamics in chronic liver disease that can be used to explore the regulatory role of iHSCs in liver homeostasis. Moreover, our model can also be generalized to fibroblasts during repair and fibrosis in other tissues.

Site-graph rewriting languages, such as Kappa or BNGL, offer parsimonious ways to describe highly combinatorial systems of mechanistic interactions among proteins. These systems may be then simulated efficiently. Yet, the modeling mechanisms that involve counting (a number of phosphorylated sites for instance) require an exponential number of rules in Kappa. In BNGL, updating the set of the potential applications of rules in the current state of the system comes down to the sub-graph isomorphism problem (which is NP-complete). In this paper, we extend Kappa to deal both parsimoniously and efficiently with counters. We propose a single push-out semantics for Kappa with counters. We show how to compile Kappa with counters into Kappa without counters (without requiring an exponential number of rules). We design a static analysis, based on affine relationships, to identify the meaning of counters and bound their ranges accordingly.

Presents the introductory editorial for this issue of the publication.

Motivation: We present an overview of the Kappa platform, an integrated suite of analysis and visualization techniques for building and interactively exploring rule-based models. The main components of the platform are the Kappa Simulator, the Kappa Static Analyzer and the Kappa Story Extractor. In addition to these components, we describe the Kappa User Interface, which includes a range of interactive visualization tools for rule-based models needed to make sense of the complexity of biological systems. We argue that, in this approach, modeling is akin to programming and can likewise benefit from an integrated development environment. Our platform is a step in this direction. Results: We discuss details about the computation and rendering of static, dynamic, and causal views of a model, which include the contact map (CM), snaphots at different resolutions, the dynamic influence network (DIN) and causal compression. We provide use cases illustrating how these concepts generate insight. Specifically, we show how the CM and snapshots provide information about systems capable of polymerization, such as Wnt signaling. A well-understood model of the KaiABC oscillator, translated into Kappa from the literature, is deployed to demonstrate the DIN and its use in understanding systems dynamics. Finally, we discuss how pathways might be discovered or recovered from a rule-based model by means of causal compression, as exemplified for early events in EGF signaling. Availability and implementation: The Kappa platform is available via the project website at kappalanguage.org. All components of the platform are open source and freely available through the authors' code repositories.

Thanks to rule-based modelling languages, we can assemble large sets of mechanistic protein-protein interactions within integrated models. Our goal would be to understand how the behavior of these systems emerges from these low-level interactions. Yet, this is a quite long term challenge and it is desirable to offer intermediary levels of abstraction, so as to get a better understanding of the models and to increase our confidence within our mechanistic assumptions. To this extend, static analysis can be used to derive various abstractions of the semantics, each of them offering new perspectives on the models. We propose an abstract interpretation of the behavior of each protein, in isolation. Given a model written in Kappa, this abstraction computes for each kind of proteins a transition system that describes which conformations this protein may take and how a protein may pass from one conformation to another one. Then, we use simplicial complexes to abstract away the interleaving order of the transformations between conformations that commute. As a result, we get a compact summary of the potential behavior of each protein of the model.

In this paper, we introduce a novel way of constructing concise causal histories (pathways) to represent how specified structures are formed during simulation of systems represented by rule-based models. This is founded on a new, clean, graph-based semantics introduced in the first part of this paper for Kappa, a rule-based modelling language that has emerged as a natural description of protein-protein interactions in molecular biology [Bachman 2011]. The semantics is capable of capturing the whole of Kappa, including subtle side-effects on deletion of structure, and its structured presentation provides the basis for the translation of techniques to other models. In particular, we give a notion of trajectory compression, which restricts a trace culminating in the production of a given structure to the actions necessary for the structure to occur. This is central to the reconstruction of biochemical pathways due to the failure of traditional techniques to provide adequately concise causal histories, and we expect it to be applicable in a range of other modelling situations.

Rule-based approaches (as in our own Kappa, or the BNG language, or many other propositions allowing the consideration of "reaction classes'') offer new and more powerful ways to capture the combinatorial interactions that are typical of molecular biological systems. They afford relatively compact and faithful descriptions of cellular interaction networks despite the combination of two broad types of interaction: the formation of complexes (a biological term for the ubiquitous non-covalent binding of bio-molecules), and the chemical modifications of macromolecules (aka post-translational modifications). However, all is not perfect. This same combinatorial explosion that pervades biological systems also seems to prevent the simulation of molecular networks using systems of differential equations. In all but the simplest cases the generation (and even more the integration) of the explicit system of differential equations which is canonically associated to a rule set is unfeasible. So there seems to be a price to pay for this increase in clarity and precision of the description, namely that one can only execute such rule-based systems using their stochastic semantics as continuous time Markov chains, which means a slower if more accurate simulation. In this paper, we take a fresh look at this question, and, using techniques from the abstract interpretation framework, we construct a reduction method which generates (typically) far smaller systems of differential equations than the concrete/canonical one. We show that the abstract/reduced differential system has solutions which are linear combinations of the canonical ones. Importantly, our method: 1) does not require the concrete system to be explicitly computed, so it is intensional, 2) nor does it rely on the choice of a specific set of rate constants for the system to be reduced, so it is symbolic, and 3) achieves good compression when tested on rule-based models of significant size, so it is also realistic.

We discuss the characteristic properties of ASTREE, an automatic static analyzer for proving the absence of runtime errors in safety-critical real-time synchronous control command C programs, and compare it with a variety of other program analysis tools.

We show that abstract interpretation-based static program analysis can be made efficient and precise enough to formally verify a class of properties for a family of large programs with few or no false alarms. This is achieved by refinement of a general purpose static analyzer and later adaptation to particular programs of the family by the end-user through parametrization. This is applied to the proof of soundness of data manipulation operations at the machine level for periodic synchronous safety critical embedded software.The main novelties are the design principle of static analyzers by refinement and adaptation through parametrization (Sect. 3 and 7), the symbolic manipulation of expressions to improve the precision of abstract transfer functions (Sect. 6.3), the octagon (Sect. 6.2.2), ellipsoid (Sect. 6.2.3), and decision tree (Sect. 6.2.4) abstract domains, all with sound handling of rounding errors in oating point computations, widening strategies (with thresholds: Sect. 7.1.2, delayed: Sect. 7.1.3) and the automatic determination of the parameters (parametrized packing: Sect. 7.2).